package cs271.examples.sorting;


/**
 * From 'Data Structures and Algorithms Analysis in Java'
 * by Mark Allen Weiss
 * 
 * see http://www.cs.fiu.edu/~weiss/dsaajava2/code/Sort.java
 */
public class InsertionSort {

	public static int insertionSort(int[] array) {
		int j;

		int ops = 0;

		for(int p=1; p<array.length; p++) {
			int tmp = array[p];
			for(j=p; j>0 && array[j-1]>tmp; j--) {
				array[j] = array[j-1];
				ops++;
			}
			array[j] = tmp;
			ops++;
		}
		return ops;
	}

	public static int insertionSort(Comparable[] array) {
		int j;

		int ops = 0;

		for(int p=1; p<array.length; p++) {
			Comparable tmp = array[p];

			for(j=p; j>0 && tmp.compareTo(array[j-1])<0; j--) {
				array[j] = array[j-1];
				ops++;
			}
			array[j] = tmp;
			ops++;
		}
		return ops;
	}

	public static void main(String[] args) {
		int[] unsorted = new int[] { 40,23, 38, 5, 106};
		int ops = insertionSort(unsorted);
		for(int i: unsorted)
			System.out.print(i +", ");
		System.out.println("\nOps: " + ops);

		int[] sorted = new int[] { 5, 23, 38, 40, 106};
		ops = insertionSort(sorted);
		for(int i: sorted)
			System.out.print(i +", ");
		System.out.println("\nOps: " + ops);

		String[] unsortedStrings = new String[] { "z", "d", "q", "p", "M"};
		ops = insertionSort(unsortedStrings);
		for(String i: unsortedStrings)
			System.out.print(i +", ");
		System.out.println("\nOps: " + ops);
	}
}
